package dp.practice3.long_subsequence;

import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String A = "aabdcc";
        String B = "efaajhcc";
        System.out.println(subsequence(A, B));
    }

    private static int subsequence(String A, String B) {
        if (A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }
        int lenOfA = A.length();
        int lenOfB = B.length();
        int[][] count = new int[lenOfB][lenOfA];
        int max = 0;
        //初始状态
        for (int i = 0; i < lenOfA; i++) {
            if (A.charAt(i) == B.charAt(0)) {
                count[0][i] = 1;
                max = 1;
            }
        }
        //状态传递
        for (int i = 1; i < lenOfB; i++) {
            for (int j = 0; j < lenOfA; j++) {
                if (B.charAt(i) == A.charAt(j)) {
                    count[i][j] = Max(count, i - 1, j - 1) + 1;
                    if (count[i][j] > max) {
                        max = count[i][j];
                    }
                }
            }
        }
        List<int[]> list = Arrays.asList(count);
        list.forEach(e -> {
            System.out.println(Arrays.toString(e));
        });
        return max;
    }

    private static int Max(int[][] arr, int end1, int end2) {
        if (end2 < 0) {
            return 0;
        }
        int max = arr[0][0];
        for (int i = 0; i <= end1; i++) {
            for (int j = 0; j <= end2; j++) {
                if (arr[i][j] > max) {
                    max = arr[i][j];
                }
            }
        }
        return max;
    }
}
